package main

func main() {
	// [203. 移除链表元素](https://leetcode.cn/problems/remove-linked-list-elements/)
	// [707. 设计链表](https://leetcode.cn/problems/design-linked-list/)
	// [206. 反转链表](https://leetcode.cn/problems/reverse-linked-list/)
	// [24. 两两交换链表中的节点](https://leetcode.cn/problems/swap-nodes-in-pairs/)
	// [19. 删除链表的倒数第 N 个结点](https://leetcode.cn/problems/remove-nth-node-from-end-of-list/)

}

// 203
func removeElements(head *ListNode, val int) *ListNode {
	dummy := &ListNode{0, head}
	cur := dummy
	for cur.Next != nil {
		if cur.Next.Val == val {
			cur.Next = cur.Next.Next
		} else {
			cur = cur.Next
		}
	}
	return dummy.Next
}

// 707
type MyLinkedList struct {
	dummy *Node
	size  int
}

type Node struct {
	val  int
	next *Node
}

func Constructor() MyLinkedList {
	return MyLinkedList{&Node{}, -1}
}

func (this *MyLinkedList) Get(index int) int {
	if index < 0 || index > this.size {
		return -1
	}
	cur := this.dummy
	for i := 0; i <= index; i++ {
		cur = cur.next
	}
	return cur.val
}

func (this *MyLinkedList) AddAtHead(val int) {
	newnode := &Node{val, this.dummy.next}
	this.dummy.next = newnode
	this.size++
}

func (this *MyLinkedList) AddAtTail(val int) {
	newnode := &Node{val, nil}
	this.size++
	cur := this.dummy
	for cur.next != nil {
		cur = cur.next
	}
	cur.next = newnode
}

func (this *MyLinkedList) AddAtIndex(index int, val int) {
	if index < 0 {
		this.AddAtHead(val)
	} else if index == this.size+1 {
		this.AddAtTail(val)
	} else if index > this.size+1 {
		return
	} else {
		cur := this.dummy
		this.size++
		for i := 0; i < index; i++ {
			cur = cur.next
		}
		newnode := &Node{val, cur.next}
		cur.next = newnode
	}
}

func (this *MyLinkedList) DeleteAtIndex(index int) {
	if index < 0 || index > this.size {
		return
	}
	this.size--
	cur := this.dummy
	var pre *Node
	for i := 0; i <= index; i++ {
		pre = cur
		cur = cur.next
	}
	pre.next = cur.next
}

// 206
func reverseList(head *ListNode) *ListNode {
	dummy := &ListNode{0, nil}
	cur := head
	for cur != nil {
		tmp := cur.Next
		cur.Next = dummy.Next
		dummy.Next = cur
		cur = tmp
	}
	return dummy.Next
}

// 24
func swapPairs(head *ListNode) *ListNode {
	dummy := &ListNode{0, head}
	cur := dummy
	for cur.Next != nil && cur.Next.Next != nil {
		node1 := cur.Next
		node2 := cur.Next.Next
		node3 := cur.Next.Next.Next

		cur.Next = node2
		node2.Next = node1
		node1.Next = node3
		cur = node1
	}
	return dummy.Next
}

// 19
func removeNthFromEnd(head *ListNode, n int) *ListNode {
	dummy := &ListNode{0, head}
	fast, slow := dummy, dummy
	for i := 0; i < n; i++ {
		fast = fast.Next
	}
	for fast.Next != nil {
		fast = fast.Next
		slow = slow.Next
	}
	slow.Next = slow.Next.Next
	return dummy.Next
}
